#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX_VISIRNUM 100   // 最大访问序列长度

// 函数：显示访问序列
void ShowVisit(int a[],int num)
{
	printf("访问序列:"); 
	for(int i=0;i<num;i++)
	{
          printf("%2d",a[i]);
	}
	printf("\n");
}

// 函数：显示内存块的当前状态
void ShowRam(int a[],int num)
{
	printf("内存块:"); 
	for(int i=0;i<num;i++)
	{
          printf("%3d",a[i]);
	}
	printf("\n");
}

// 函数：显示最终结果（页面置换和缺页统计）
void ShowFinal(int replaceNum,int lackingNum,int VisitNum)
{
	printf("\n缺页次数：%3d\n",lackingNum);
	printf("置换次数：%3d\n",replaceNum);
	printf("缺页率：%.2f%%\n",lackingNum*1.0/VisitNum*100);
	printf("命中率: %.2f%%\n",(1-lackingNum*1.0/VisitNum)*100);
}

// 函数：初始化数组为-1 
void Init(int a[],int num)
{for(int i=0;i<num;i++){a[i]=-1; }} 
 
 // 函数：查找访问序列中某页面未来的出现位置
int searchfuture(int fork[] ,int now,int VisitNum,int nowmessage)
{
	int i =now+1;
	for(i;i<VisitNum;i++)
	{
		if(fork[i]==nowmessage)
		{
			return i;
		 } 
	} 
	return 1000;// 表示未找到的大数
}

// FIFO页面置换算法
void FIFO(int fork[], int PageNum, int PhyNum, int VisitNum)
{
	printf("*************FIFO算法*************\n");
	int ram[PhyNum]; Init(ram,PhyNum);// 初始化物理内存数组
	int point=0;// FIFO当前位置指针
	int judge=-1;// 用于标记页面是否在内存中的变量，-1 表示不在内存中
	int replaceNum = 0;//置换次数 
    int lackingNum = 0;//缺页次数 
    for(int i =0;i<VisitNum;i++)// 遍历访问页面的次数
	{
		for(int j=0;j<PhyNum;j++)// 遍历物理内存中的页面槽
		{
			if(ram[j]==fork[i]) //如果当前访问的页面在内存中一旦在内存之内，直接输出 
			{
				printf("访问内存%d：",fork[i]);
	           	ShowRam(ram,PhyNum);
	           	judge=1;// 内存中存在页面
				break; 
			}
			if(ram[j]==-1)//不在内存之中并且没有满 ，也直接输出 
			{
				ram[j]=fork[i];
				lackingNum++; 
				printf("访问内存%d：",fork[i]);
		        ShowRam(ram,PhyNum);
		        judge=1;// 内存中找到空槽
				break; 
			}
		}
		if(judge==-1){ 
		ram[point]=fork[i];                    //在内存之内并且已经满了，FIFO置换 ，FIFO置换最早进入的页面
		point=(point+1)%PhyNum;                // 更新FIFO指针
		replaceNum++;
		lackingNum++;
		printf("访问内存%d：",fork[i]);
		ShowRam(ram,PhyNum);
	 	}
	 	judge=-1; 
	 } 
	 ShowFinal( replaceNum, lackingNum, VisitNum);  // 显示最终的置换次数、缺页次数等信息
} 
 
 // LRU页面置换算法
void LRU(int fork[], int PageNum, int PhyNum, int VisitNum)
{
	printf("*************LRU算法*************\n");
	int ram[PhyNum];Init(ram,PhyNum);// 物理内存数组
	int time[PhyNum];Init(time,PhyNum);//time记录的是已经有的块号多久没使用了 
    int judge=-1;// 用于标记页面是否在内存中的变量，-1 表示不在内存中
	int replaceNum = 0;//置换次数 
    int lackingNum = 0;//缺页次数 
    
    for(int i =0;i<VisitNum;i++)// 遍历访问页面的次数
	{
		for (int k=0;k<PhyNum;k++)// 遍历物理内存中的页面槽，增加未使用时间
		{
			if(time[k]!=-1){time[k]++;}
		}
		for(int j=0;j<PhyNum;j++)// 遍历物理内存中的页面槽
		{
			if(ram[j]==fork[i]) ///如果当前访问的页面在内存中，一旦在内存之内，直接输出 
			{
				printf("访问内存%d：",fork[i]);
	           	ShowRam(ram,PhyNum);
	           	printf("time:");
				time[j]=0;// 重置该页面的未使用时间
				for(int op=0;op<PhyNum;op++){printf("%2d",time[op]);}
				printf("\n");
	           	judge=1;
				break; 
			}
			if(ram[j]==-1)//不在内存之中并且没有满 ，也直接输出 
			{
				ram[j]=fork[i];
				lackingNum++; 
				printf("访问内存%d：",fork[i]);
		        ShowRam(ram,PhyNum);
		        time[j]=0;
		        judge=1;
				printf("time:");
				for(int op=0;op<PhyNum;op++){printf("%2d",time[op]);}
				printf("\n");
				break; 
			}
		}
		if(judge==-1){                     //在内存之内并且已经满了，LRU置换 
		int max=0;
		for (int k=0;k<PhyNum;k++)// 找出未使用时间最长的页面
		{
			if(time[k]>time[max])
			max=k;
		}
		ram[max]=fork[i];
        time[max] = 0;
		replaceNum++;
		lackingNum++;
		printf("访问内存%d：",fork[i]);
		ShowRam(ram,PhyNum);
		printf("time:");
		for(int op=0;op<PhyNum;op++){printf("%2d",time[op]);}
		printf("\n");
	 	}
	 	judge=-1; 
	 } 
	 ShowFinal( replaceNum, lackingNum, VisitNum); // 显示最终的置换次数、缺页次数等信息
} 
 
void OPT(int fork[], int PageNum, int PhyNum, int VisitNum)
{
	printf("*************OPT算法*************\n");
	int ram[PhyNum];Init(ram,PhyNum);
	int future[PhyNum];Init(future,PhyNum);//future记录的是未来多久要使用到 
    int judge=-1;
	int replaceNum = 0;//置换次数 
    int lackingNum = 0;//缺页次数 
    
    for(int i =0;i<VisitNum;i++)
	{
 
		for(int j=0;j<PhyNum;j++)
		{
			if(ram[j]==fork[i]) //一旦在内存之内，直接输出 
			{
				printf("访问内存%d：",fork[i]);
	           	ShowRam(ram,PhyNum);
	           	future[j]=searchfuture(fork,i, VisitNum,ram[j]);
	           	judge=1;
				break; 
			}
			if(ram[j]==-1)//不在内存之中并且没有满 ，也直接输出 
			{
				ram[j]=fork[i];
				lackingNum++; 
				printf("访问内存%d：",fork[i]);
		        ShowRam(ram,PhyNum);
		        judge=1;
	           	future[j]=searchfuture(fork,i, VisitNum,ram[j]);
				break; 
			}
		}
		if(judge==-1){                     //在内存之内并且已经满了，LRU置换 
		int max=0;
		for (int k=0;k<PhyNum;k++)
		{
			if(future[k]>future[max])
			max=k;
		}
		ram[max]=fork[i];
        future[max] = searchfuture(fork,i, VisitNum,ram[max]);
		replaceNum++;
		lackingNum++;
		printf("访问内存%d：",fork[i]);
		ShowRam(ram,PhyNum);
	 	}
	 	judge=-1; 
	 } 
	 ShowFinal( replaceNum, lackingNum, VisitNum); 
    
    
}
 
void CLOCK(int fork[], int PageNum, int PhyNum, int VisitNum)
{

	printf("*************CLOCK算法*************\n");
	int ram[PhyNum];Init(ram,PhyNum);
	int clock[PhyNum];
	int replaceNum = 0;//置换次数 
    int lackingNum = 0;//缺//time记录的是访问号  
	int point=0;//指向循环队列中当前的位置
	int num=0;//统计循环查找的次数
	int NUM=0;//初始内存块有没有满  
	for(int pp =0;pp<PhyNum;pp++){clock[pp]=0;} 
    int judge=-1;   
    for(int i =0;i<VisitNum;i++)
	{	
		if(NUM!=PhyNum)
		{ 
			for(int j=0;j<PhyNum;j++)
			{
				if(ram[j]==fork[i]) //初始内存没满的时候，一旦在内存之内，直接输出 
				{
					printf("访问内存%d：",fork[i]);
	       	    	ShowRam(ram,PhyNum);
	       	    	clock[j]=1;
					printf("1clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n"); 
	       	    	judge=1;
					break; 
				}
				if(ram[j]==-1)//初始内存没满的时候，不在内存之中并且没有满 ，也直接输出 
				{ NUM++;
				  ram[j]=fork[i];
				  lackingNum++; 
			      printf("访问内存%d：",fork[i]);
		     	  ShowRam(ram,PhyNum);
		      	  clock[j]=1;
		      	  printf("2clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n");
		      	  judge=1;
			      break; 
				}
			}
		}
		else
		{   num=0;
			while(num!=PhyNum)
			{	
				if(ram[point]==fork[i]) //初始内存已经满了，一旦在内存之内，直接输出 
				{
				printf("访问内存%d：",fork[i]);
	           	ShowRam(ram,PhyNum);
	           	clock[point]=1;
				printf("3clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n"); 
	           	judge=1;
	           	point=(point+1)%PhyNum;	
				break; 
				}
				num++;
				point=(point+1)%PhyNum;
			}
			int num=0;
			if(judge==-1)
			{     //-1说明不在内存中，1代表在内存中 
			while(num!=PhyNum)//第一遍循环找访问为0；
			{	
				if(clock[point]==0)
				{
					ram[point]=fork[i];
					clock[point]=1;
					replaceNum++;
			   		lackingNum++;//页次数 
			   		printf("访问内存%d：",fork[i]);
					ShowRam(ram,PhyNum);
					printf("4clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n");
					point=(point+1)%PhyNum;	
					break;
				 }
				point=(point+1)%PhyNum;
				num++; 	
			}
			
			if(num==PhyNum)
			{   
				for(int pp =0;pp<PhyNum;pp++){clock[pp]=0;}//第二遍循环先将访问为都置为0，再一个个找过去 
				ram[point]=fork[i];
				clock[point]=1;
				point=(point+1)%PhyNum;
				printf("访问内存%d：",fork[i]);
			    ShowRam(ram,PhyNum);
				printf("5clock:");for(int op=0;op<PhyNum;op++){printf("%2d",clock[op]);}printf("\n");
				replaceNum++;
			   	lackingNum++;
			}
		 	}
	 	}
	 	
	 	judge=-1;
	}	
	ShowFinal( replaceNum, lackingNum, VisitNum); 	  
}
 
int main()
{
	
	printf("*************页面置换算法*************\n");
	
	int PageNum;                 //页面数量 
	int PhyNum;                 //物理块数量  
	int VisitNum;              //访问序列的长度
	int Visit[MAX_VISIRNUM];
	printf("请输入页面数量\n");
	scanf("%d",&PageNum);
	printf("请输入内存物理块数\n");
	scanf("%d",&PhyNum);
	printf("请输入访问序列长度\n");
	scanf("%d",&VisitNum);	
	
	srand((unsigned)time(NULL));      //随机访问序列 
	for(int i =0;i<VisitNum;i++)
	{
		Visit[i]=rand()%PageNum;
	}
	ShowVisit(Visit,VisitNum);
	
    while (1) {
		int fork[VisitNum];          //fork数组就是复制了Visit数组，相当于初始化随机序列 
		for(int i =0;i<VisitNum;i++)
		{
			fork[i]=Visit[i];
		} 
        printf("请选择你想使用的置换算法:\n");
        printf("1.FIFO 2.LRU 3.OPT 4.CLOCK 5.Over\n");
        int want;
        scanf("%d",&want);
        switch (want) {
            case 1:
            	ShowVisit(Visit,VisitNum);
                FIFO(fork, PageNum, PhyNum, VisitNum);printf("\n"); 
                break;
            case 2:
                ShowVisit(Visit,VisitNum);
                LRU(fork, PageNum, PhyNum, VisitNum); printf("\n"); 
                break;
            case 3:
                ShowVisit(Visit,VisitNum);
                OPT(fork, PageNum, PhyNum, VisitNum);printf("\n"); 
                break;
            case 4:
                ShowVisit(Visit,VisitNum);
                CLOCK(fork, PageNum, PhyNum, VisitNum);printf("\n"); 
                break;		 
			case 5:
			   printf("结束运行,谢谢观看！");
               printf("\n"); 
               exit(0);
               break;
            default:
                printf("越界!,请重新输入\n");
                break;    
        }
    }
    return 0;
 } 